package binaryTree;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

//        第一步：如果数组大小为零的话，说明是空节点了。
//
//        第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
//
//        第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
//
//        第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
//
//        第五步：切割后序数组，切成后序左数组和后序右数组
//
//        第六步：递归处理左区间和右区间
public class InorderPostorderConstructTree18 {
//这是答案
    Map<Integer, Integer> map;  // 方便根据数值查找位置
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }

        return findNode(inorder,  0, inorder.length, postorder,0, postorder.length);  // 前闭后开
    }

    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        // 参数里的范围都是前闭后开
        if (inBegin >= inEnd || postBegin >= postEnd) {  // 不满足左闭右开，说明没有元素，返回空树
            return null;
        }
        int rootIndex = map.get(postorder[postEnd - 1]);  // 找到后序遍历的最后一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
        int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数，用来确定后序数列的个数
        root.left = findNode(inorder, inBegin, rootIndex,
                postorder, postBegin, postBegin + lenOfLeft);
        root.right = findNode(inorder, rootIndex + 1, inEnd,
                postorder, postBegin + lenOfLeft, postEnd - 1);

        return root;
    }




    //根据中序和后序遍历顺序 构造二叉树
    public TreeNode buildTree1(int[] inorder, int[] postorder) {
        if (postorder.length==0){
            return  null;
        }
        //在后序中找到根节点
        int rootVal=postorder[postorder.length-1];
        TreeNode root = new TreeNode(rootVal);
        if (postorder.length==1){
            return  root;
        }
        //在中序中找到切割点
        int index=0;
        for ( index = 0; index < inorder.length ; index++) {
            if (inorder[index]==rootVal){
                break;
            }
        }
        //计算左中序的长度
        //计算右中序的长度
        // 切分中序数组
        int[]  leftInorder=new int[index];
        int[]    rightInorder=new int[inorder.length-index-1];
        int m=0;
        int n=0;
        for (int i = 0; i < inorder.length; i++) {
            if (i<index&&m<index){
                leftInorder[m]=inorder[i];
                m++;
            }
            if (i==index){
                continue;
            }
            if (i>index&&n<inorder.length-index-1){
                rightInorder[n]=inorder[i];
                n++;
            }
        }

//       切后序数组
        int[]  leftPostorder=new int[index];
        int[]    rightPostorder=new int[inorder.length-index-1];
        int r=0;
        int k=0;
        for (int i = 0; i < postorder.length; i++) {
            if (i<index&&r<index){
                leftPostorder[r]=postorder[i];
                r++;
            }
            if (i>=index&&k<inorder.length-index-1){
                rightPostorder[k]=postorder[i];
                k++;
            }
        }
        root.left=buildTree1(leftInorder,leftPostorder);
        root.right=buildTree1(rightInorder,rightPostorder);
        return  root;
    }


    //根据中序和前序遍历顺序 构造二叉树
    public TreeNode buildTree2(int[] preorder, int[] inorder) {
        if (preorder.length==0){
            return  null;
        }
        //在前序中找到根节点
        int rootVal=preorder[0];
        TreeNode root = new TreeNode(rootVal);
        if (preorder.length==1){
            return  root;
        }
        //在中序中找到切割点
        int index=0;
        for ( index = 0; index < inorder.length ; index++) {
            if (inorder[index]==rootVal){
                break;
            }
        }
        // 切分中序数组
        int[]  leftInorder=new int[index];
        int[]    rightInorder=new int[inorder.length-index-1];
        int m=0;
        int n=0;
        for (int i = 0; i < inorder.length; i++) {
            if (i<index&&m<index){
                leftInorder[m]=inorder[i];
                m++;
            }
            if (i==index){
                continue;
            }
            if (i>index&&n<inorder.length-index-1){
                rightInorder[n]=inorder[i];
                n++;
            }
        }

//      切分前序数组
        int[]  leftPreorder=new int[index];
        int[]    rightPreorder=new int[preorder.length-index-1];
        int r=0;
        int k=0;
        for (int i = 1; i < preorder.length; i++) {
            if (r<index){
                leftPreorder[r]=preorder[i];
                r++;
            }
            else{
                rightPreorder[k]=preorder[i];
                k++;
            }


        }
        root.left=buildTree2(leftPreorder,leftInorder);
        root.right=buildTree2(rightPreorder,rightInorder);
        return  root;
    }




    //先序遍历
    public  void preOrderTraver(TreeNode root, ArrayList list){
        if (root==null){
            return;
        }
        list.add(root.val);
        preOrderTraver(root.left,list);
        preOrderTraver(root.right,list);
    }





    public static void main(String[] args) {
        InorderPostorderConstructTree18 inorderPostorderConstructTree18 = new InorderPostorderConstructTree18();
        int[]  inorder={9,3,15,20,7};
        int[]  preorder={3,9,20,15,7};
        TreeNode root = inorderPostorderConstructTree18.buildTree2(preorder,inorder);
        ArrayList<Integer> list = new ArrayList<>();
        inorderPostorderConstructTree18.preOrderTraver(root,list);
        for (int a:
             list) {
            System.out.println(a);
        }



    }
}
